package com.sheng.leetcode.year2023.month09.day14;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author by ls
 * @date 2023/9/14
 * <p>
 * 1222. 可以攻击国王的皇后<p>
 * <p>
 * 在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。<p>
 * 给定一个由整数坐标组成的数组 queens ，表示黑皇后的位置；以及一对坐标 king ，<p>
 * 表示白国王的位置，返回所有可以攻击国王的皇后的坐标(任意顺序)。<p>
 * <p>
 * 示例 1：<p>
 * 输入：queens = {{0,1},{1,0},{4,0},{0,4},{3,3},{2,4}}, king = {0,0}<p>
 * 输出：{{0,1},{1,0},{3,3}}<p>
 * 解释：<p>
 * {0,1} 的皇后可以攻击到国王，因为他们在同一行上。<p>
 * {1,0} 的皇后可以攻击到国王，因为他们在同一列上。<p>
 * {3,3} 的皇后可以攻击到国王，因为他们在同一条对角线上。<p>
 * {0,4} 的皇后无法攻击到国王，因为她被位于 {0,1} 的皇后挡住了。<p>
 * {4,0} 的皇后无法攻击到国王，因为她被位于 {1,0} 的皇后挡住了。<p>
 * {2,4} 的皇后无法攻击到国王，因为她和国王不在同一行/列/对角线上。<p>
 * <p>
 * 示例 2：<p>
 * 输入：queens = {{0,0},{1,1},{2,2},{3,4},{3,5},{4,4},{4,5}}, king = {3,3}<p>
 * 输出：{{2,2},{3,4},{4,4}}<p>
 * <p>
 * 示例 3：<p>
 * 输入：queens = {{5,6},{7,7},{2,1},{0,7},{1,6},{5,1},{3,7},{0,3},{4,0},{1,2},{6,3},{5,0},{0,4},{2,2},{1,1},{6,4},{5,4},{0,0},{2,6},{4,5},{5,2},{1,4},{7,5},{2,3},{0,5},{4,2},{1,0},{2,7},{0,1},{4,6},{6,1},{0,6},{4,3},{1,7}}, king = {3,4}
 * 输出：{{2,3},{1,4},{1,6},{3,7},{4,3},{5,4},{4,5}}<p>
 * 0    0   0   0   0   0   0   0
 * 0    0   0   0   0   0   0   0
 * 0    0   0   0   0   0   0   0
 * 0    0   2   0   2   0   0   0
 * 0    2   0   1   0   2   0   0
 * 0    0   0   0   0   0   0   0
 * 0    2   0   0   0   0   0   0
 * 0    0   0   2   0   0   0   0
 * <p>
 * 提示：<p>
 * 1 <= queens.length <= 63<p>
 * queens{i}.length == 2<p>
 * 0 <= queens{i}{j} < 8<p>
 * king.length == 2<p>
 * 0 <= king{0}, king{1} < 8<p>
 * 一个棋盘格上最多只能放置一枚棋子。<p>
 */
public class LeetCode1222 {

    @Test
    public void test01() {
//        int[][] queens = {{0, 1}, {1, 0}, {4, 0}, {0, 4}, {3, 3}, {2, 4}};
//        int[] king = {0, 0};
//        int[][] queens = {{0, 0}, {1, 1}, {2, 2}, {3, 4}, {3, 5}, {4, 4}, {4, 5}};
//        int[] king = {3, 3};
        int[][] queens = {{5, 6}, {7, 7}, {2, 1}, {0, 7}, {1, 6}, {5, 1}, {3, 7}, {0, 3}, {4, 0}, {1, 2}, {6, 3}, {5, 0}, {0, 4}, {2, 2}, {1, 1}, {6, 4}, {5, 4}, {0, 0}, {2, 6}, {4, 5}, {5, 2}, {1, 4}, {7, 5}, {2, 3}, {0, 5}, {4, 2}, {1, 0}, {2, 7}, {0, 1}, {4, 6}, {6, 1}, {0, 6}, {4, 3}, {1, 7}};
        int[] king = {3, 4};
        System.out.println(new Solution().queensAttacktheKing(queens, king));
    }
}

class Solution {
    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        // 黑皇后 queens[i] 与白国王 king 处于同一行/列/对角线上，且中间没有阻拦时可以攻击到白国王 king
        // 即：queens[i][0] == king[0] || queens[i][1] == king[1] || (Math.abs(queens[i][0] - king[0]) == Math.abs(queens[i][1] - king[1])) 这种情况满足任意一种即可进行下一次判断
        // 同一行/列/对角线中，选择距离国王最近的不同方位的两个点即可，最多只有 8 个黑皇后可以攻击到白国王
        List<List<Integer>> list = new ArrayList<>();

        boolean[][] b = new boolean[8][8];
        for (int[] queen : queens) {
            // 存在黑皇后时
            b[queen[0]][queen[1]] = true;
        }
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i != 0 || j != 0) {
                    int x = king[0] + i, y = king[1] + j;
                    while (x >= 0 && x < 8 && y >= 0 && y < 8) {
                        if (b[x][y]) {
                            list.add(Arrays.asList(x, y));
                            break;
                        }
                        x += i;
                        y += j;
                    }
                }
            }
        }

//        int[][] nums = new int[8][2];
//        for (int[] num : nums) {
//            Arrays.fill(num, -1);
//        }
//        for (int[] queen : queens) {
//            if (queen[0] == king[0]) {
//                // 位于同一列
//                if (queen[1] < king[1]) {
//                    // 位于白国王上方
//                    if (nums[0][0] == -1 || nums[0][1] < queen[1]) {
//                        nums[0] = queen;
//                    }
//                } else {
//                    // 位于白国王下方
//                    if (nums[1][0] == -1 || nums[1][1] > queen[1]) {
//                        nums[1] = queen;
//                    }
//                }
//            } else if (queen[1] == king[1]) {
//                // 位于同一行
//                if (queen[0] < king[0]) {
//                    // 位于白国王左方
//                    if (nums[2][0] == -1 || nums[2][0] < queen[0]) {
//                        nums[2] = queen;
//                    }
//                } else {
//                    // 位于白国王右方
//                    if (nums[3][0] == -1 || nums[3][0] > queen[0]) {
//                        nums[3] = queen;
//                    }
//                }
//            } else if (king[0] - queen[0] == king[1] - queen[1]) {
//                // 位于从左上到右下的对角线上
//                if (queen[0] < king[0]) {
//                    // 位于左上
//                    if (nums[4][0] == -1 || nums[4][0] < queen[0]) {
//                        nums[4] = queen;
//                    }
//                } else {
//                    // 位于右下
//                    if (nums[5][0] == -1 || nums[5][0] > queen[0]) {
//                        nums[5] = queen;
//                    }
//                }
//            } else if (king[0] - queen[0] == queen[1] - king[1]) {
//                // 位于从右上到左下的对角线上
//                if (queen[1] < king[1]) {
//                    // 位于右上
//                    if (nums[6][0] == -1 || nums[6][0] > queen[0]) {
//                        nums[6] = queen;
//                    }
//                } else {
//                    // 位于右下
//                    if (nums[7][0] == -1 || nums[7][0] < queen[0]) {
//                        nums[7] = queen;
//                    }
//                }
//            }
//        }
//        for (int[] num : nums) {
//            if (num[0] != -1) {
//                List<Integer> list1 = new ArrayList<>();
//                list1.add(num[0]);
//                list1.add(num[1]);
//                list.add(list1);
//            }
//        }
        return list;
    }
}
